home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / p4 / p4-1_2c.lha / p4-1.2c / monitors / adquad.c < prev    next >
C/C++ Source or Header  |  1993-05-24  |  11KB  |  457 lines
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include "p4.h"
  4.     
  5.     /*  NOTE: This program contains some features which are more
  6.     general than required for this specific task.  Please
  7.     remember that we hope to use this as a more-or-less
  8.     prototypical use of trees in numeric algorithms.  For
  9.     example, the definition of tree_node includes "first_child"
  10.     and "sibling" pointers, although they are never actually
  11.     used (and, the tree could in any event just be
  12.     a binary tree, rather than a binary tree representing
  13.     a general tree).  Our intent is to discuss the topics
  14.     of "general trees", "representing general trees with
  15.     binary trees", etc.  It is also the case that the
  16.     use of queue_nodes is unnecessary; you could just
  17.     add a link field to the tree_nodes and queue the
  18.     ready tree_nodes in the pool.  
  19.     */
  20.     
  21.     /* this structure gives the format of a node in the tree
  22.        representing the gradual subdivision of the interval.
  23.        Each node represented a portion of the interval from
  24.        "xl" to "xr".
  25.        */
  26.  
  27. int queue_node();
  28.  
  29. struct tree_node {
  30.     double xl;        /* the left bound */
  31.     double xm;        /* the midpoint */
  32.     double xr;        /* the right bound */
  33.     double yl,ym,yr;    /* values of the function */
  34.     double integral;    /* computed value of the integral */
  35.     int status;            /* 0->not subdivided;
  36.                1->one side completed
  37.                2->both sides completed
  38.                
  39.                another way to think of this field is
  40.                as a count of the number of subcalculations
  41.                that have been completed
  42.                */
  43.     struct tree_node *parent; /* pointer to the parent node */
  44.     struct tree_node *first_child,*sibling;
  45.     p4_lock_t t_lock;
  46. };
  47.  
  48. struct queue_node {
  49.     struct queue_node *next; /* link to next node in pool or q_avail */
  50.     struct tree_node *node;  /* when node is in pool, this field points
  51.                 to a node in the tree that has been
  52.                 queued in the "pool" of work.
  53.                 */
  54. };
  55.  
  56. /* variables
  57.    
  58.    tree     - the tree representing the current state
  59.    of the computation
  60.    
  61.    pool     - the pool of problems.  Initially, only one node
  62.    will be in the pool, and it will represent the
  63.    entire interval
  64.    
  65.    q_avail  - avail-list for queue nodes
  66.    
  67.    t_avail  - avail-list for tree nodes
  68.    
  69.    numprocs - number of processes to participate in the
  70.    calculation
  71.    
  72.    normdiff - the error you are willing to tolerate in a
  73.    unit interval
  74.    */
  75.  
  76. struct globmem {
  77.     
  78.     p4_lock_t TAVL;
  79.     struct tree_node *t_avail;  /* list of available tree_nodes */
  80.     struct tree_node *tree;     /* the tree being built */
  81.     
  82.     p4_lock_t QAVL;
  83.     struct queue_node *q_avail; /* list of available queue_nodes */
  84.     struct queue_node *pool;    /* pool of available work */
  85.     
  86.     int numprocs;        /* number of processes */
  87.     double normdiff;        /* absolute amount of tolerable error */
  88.     
  89.     p4_askfor_monitor_t MO;
  90. } *glob;
  91.  
  92.  
  93. slave()
  94. {
  95.     work();
  96. }
  97.  
  98. main(argc,argv)
  99. int argc;
  100. char **argv;
  101. {
  102.     extern slave();
  103.     char c;
  104.     double r;
  105.     int i,j;
  106.     long stime,etime;
  107.     double func();
  108.     struct tree_node *t_node;
  109.     struct tree_node *alloc_tree_node();
  110.     
  111.     
  112.     p4_initenv(&argc,argv);
  113.     glob = (struct globmem *) p4_shmalloc(sizeof(struct globmem));
  114.     
  115.     glob->t_avail = NULL;
  116.     glob->q_avail = NULL;
  117.     p4_lock_init(&(glob->TAVL));
  118.     p4_lock_init(&(glob->QAVL));
  119.     p4_askfor_init(&(glob->MO));
  120.     
  121.     t_node = alloc_tree_node(); 
  122.     glob->tree = t_node;
  123.     
  124.     printf("left boundary: ");
  125.     scanf("%lf",&(t_node->xl));
  126.     printf("right boundary: ");
  127.     scanf("%lf",&(t_node->xr));
  128.     
  129.     if (t_node->xr > 15.0)
  130.     {
  131.     printf("right boundary too big; try 15.0\n");
  132.     exit(0);
  133.     }
  134.     
  135.     /* set up original node - the midpoint, function
  136.        values, and first approx of integral must be
  137.        stored in the node
  138.        */
  139.     t_node->xm = (t_node->xl + t_node->xr) / 2.0;
  140.     
  141.     t_node->yl = func(t_node->xl);
  142.     t_node->ym = func(t_node->xm);
  143.     t_node->yr = func(t_node->xr);
  144.     
  145.     t_node->integral = (t_node->xr - t_node->xl) *
  146.     (t_node->yl +
  147.      t_node->yr +
  148.      (4 * t_node->ym)) / 6.0;
  149.     
  150.     t_node->status = 0;
  151.     t_node->parent = NULL;
  152.     p4_lock_init(&(t_node->t_lock));
  153.     
  154.     /* stack the single node */
  155.     p4_update(&(glob->MO),queue_node,(P4VOID *) t_node);
  156.     
  157.     printf("'allowable difference' for a unit: ");
  158.     scanf("%lf",&(glob->normdiff));
  159.     printf("number of processes: ");
  160.     scanf("%d",&(glob->numprocs));
  161.     
  162.     stime = p4_clock();        /* note time includes process creation */
  163.     
  164.     /* create the slave processes */
  165.     for (i=1; i < glob->numprocs; i++) 
  166.     p4_create(slave);
  167.     
  168.     /* join the slaves in processing nodes in the pool */
  169.     work(); 
  170.     
  171.     etime = p4_clock();
  172.     
  173.     printf("integral = %lf\n",glob->tree->integral); 
  174.     printf("time = %d milliseconds\n",(etime - stime));
  175.     
  176.     p4_wait_for_end();
  177. }
  178.  
  179. int getprob(v)
  180. P4VOID **v;
  181. {
  182.     int rc = 1;   /* any non-zero means NO problem found */
  183.     struct queue_node **p;
  184.     
  185.     p = (struct queue_node **) v;
  186.     if (glob->pool != NULL)
  187.     {
  188.     *p = glob->pool;
  189.         glob->pool = glob->pool->next;
  190.     rc = 0;    /* FOUND a problem */
  191.     }
  192.     return(rc);
  193. }
  194.  
  195. P4VOID reset()
  196. {
  197. }
  198.  
  199. work()
  200. {
  201.     int rc;
  202.     struct tree_node *t_node;
  203.     struct queue_node *q_node;
  204.     int num_done = 0;
  205.     
  206.     rc = p4_askfor(&(glob->MO),glob->numprocs,getprob,(P4VOID *)&q_node,reset);
  207.     
  208.     while (rc == 0)
  209.     {
  210.     num_done++;
  211.     t_node = q_node->node;
  212.     dealloc_queue_node(q_node);
  213.     
  214.     evaluate(t_node);   /* process the node */
  215.     
  216.     rc = p4_askfor(&(glob->MO),glob->numprocs,getprob,(P4VOID *)&q_node,reset);
  217.     }
  218.     p4_dprintfl(5,"exiting work, did %d\n",num_done);
  219. }
  220.  
  221. /* evaluate processes a node, which may cause subnodes
  222.    to be created and stacked.
  223.    */
  224.  
  225. evaluate(n)
  226. struct tree_node *n;
  227. {
  228.     double xlm;  /* midpoint of left interval */
  229.     double xrm;  /* midpoint of right interval */
  230.     double leftint; /* integral of left */
  231.     double rightint; /* integral of right */
  232.     double ylm,yrm;  /* evaluated function for the midpoints */
  233.     struct tree_node *lch,*rch;  /* pointers to children */
  234.     struct tree_node *p; 
  235.     double diff;
  236.     struct tree_node *alloc_tree_node();
  237.     
  238.     /* first calculate the next level of approximation to
  239.        see whether we are close enough
  240.        */
  241.     xlm = (n->xl + n->xm) / 2;
  242.     xrm = (n->xm + n->xr) / 2;
  243.     ylm = func(xlm);
  244.     yrm = func(xrm);
  245.     leftint = (n->xm - n->xl) * ((n->yl + n->ym + (4 * ylm)) / 6);
  246.     rightint = (n->xr - n->xm) * ((n->ym + n->yr + (4 * yrm)) / 6);
  247.     
  248.     
  249.     diff = fabs(n->integral - (leftint + rightint));
  250.     
  251.     if (diff < (glob->normdiff / (n->xr - n->xl)))
  252.     {
  253.     
  254.     /* keep the more accurate estimate, and process completion
  255.        of this node
  256.        */
  257.     n->integral = leftint + rightint;
  258.     postcomp(n);
  259.     }
  260.     else
  261.     {
  262.     /* build the left node and stack it in the
  263.        pool of work to do
  264.        */
  265.     lch = alloc_tree_node();
  266.     lch->xl = n->xl;
  267.     lch->xm = xlm;
  268.     lch->xr = n->xm;
  269.     lch->yl = n->yl;
  270.     lch->ym = ylm;
  271.     lch->yr = n->ym;
  272.     lch->integral = leftint;
  273.     lch->status = 0;
  274.     lch->parent = n;
  275.     p4_lock_init(&(lch->t_lock));
  276.  
  277.     p4_update(&(glob->MO),queue_node,(P4VOID *) lch);
  278.     
  279.     /* we now process the right child */
  280.     rch = alloc_tree_node();
  281.     rch->xl = n->xm;
  282.     rch->xm = xrm;
  283.     rch->xr = n->xr;
  284.     rch->yl = n->ym;
  285.     rch->ym = yrm;
  286.     rch->yr = n->yr;
  287.     rch->integral = rightint;
  288.     rch->status = 0;
  289.     rch->parent = n;
  290.     p4_lock_init(&(rch->t_lock));
  291.     
  292.     evaluate(rch);
  293.     }
  294. }
  295.  
  296.  
  297. /* this routine handles the "completion" of a node,
  298.    which involves storing the answer in the parent node,
  299.    checking to see if this completes the parent, and processing
  300.    completion of the parent (if required).  The nodes are
  301.    returned to the avail list as they are removed from the
  302.    leaves of the tree (except the root!)
  303.    */
  304. postcomp(n)
  305. struct tree_node *n;
  306. {
  307.     struct tree_node *p;   /* pointer to parent */
  308.     int stat;         /* status of the parent */
  309.     
  310.     if ((p = n->parent) != NULL)
  311.     {
  312.     p4_lock(&(p->t_lock));
  313.     if (p->status == 0) 
  314.         p->integral = 0.000;
  315.     p->integral += n->integral;
  316.     
  317.     stat = ++(p->status);
  318.     p4_unlock(&(p->t_lock));
  319.     
  320.     dealloc_tree_node(n);
  321.     
  322.         if (stat == 2)  /* if parent is complete too */
  323.     {
  324.         postcomp(p);
  325.     }
  326.     }
  327. }
  328.  
  329. /* this is the function to integrate */
  330. double func(x)
  331. double x;
  332. {
  333.     int i;
  334.     
  335.     /* the attribute "static" assures that the values do not change
  336.        between invocations of the function.  That is, a single static
  337.        copy is allocated and referenced by all calls to the routine.
  338.        */
  339.     static int power = 30;
  340.     static int firstcall = 1;
  341.     static double factor;
  342.     static double pi;
  343.     double v;
  344.     
  345.     
  346.     if (firstcall)
  347.     {
  348.     factor = 1;
  349.     for (i=1; (i <= (power/2)); i++)
  350.         factor = factor * (1 - (.5 / i));
  351.     
  352.     pi = 4 * atan((double) 1);
  353.     firstcall = 0;
  354.     }
  355.     
  356.     return(pow(sin((double) (pi * x)),(double) power) / factor);
  357. }
  358.  
  359. /*
  360.   this routine allocates a tree_node from globally-shared
  361.   memory.
  362.   */
  363. struct tree_node *alloc_tree_node()
  364. {
  365.     struct tree_node *node;
  366.     
  367.     p4_lock(&(glob->TAVL));
  368.     if ((node = glob->t_avail) == NULL)
  369.     {
  370.     node = (struct tree_node *) p4_shmalloc(sizeof(struct tree_node));
  371.     if (node == NULL)
  372.         {
  373.             printf("*** out of memory in alloc_tree_node ***\n");
  374.             exit(3);
  375.         }
  376.     }
  377.     else
  378.     {
  379.         glob->t_avail = node->sibling;
  380.     }
  381.     p4_unlock(&(glob->TAVL));
  382.     return(node);
  383. }
  384.  
  385. /*
  386.   this routine frees a tree_node
  387.   */
  388. dealloc_tree_node(node)
  389. struct tree_node *node;
  390. {
  391.     
  392.     p4_lock(&(glob->TAVL));
  393.     node->sibling = glob->t_avail;
  394.     glob->t_avail = node;
  395.     p4_unlock(&(glob->TAVL));
  396. }
  397.  
  398. /*
  399.   this routine allocates a queue_node from globally-shared
  400.   memory.
  401.   */
  402. struct queue_node *alloc_queue_node()
  403. {
  404.     struct queue_node *node;
  405.     
  406.     p4_lock(&(glob->QAVL));
  407.     if ((node = glob->q_avail) == NULL)
  408.     {
  409.     node = (struct queue_node *) p4_shmalloc(sizeof(struct queue_node));
  410.     if (node == NULL)
  411.         {
  412.             printf("*** out of memory in alloc_queue_node ***\n");
  413.             exit(3);
  414.         }
  415.     }
  416.     else
  417.     {
  418.         glob->q_avail = node->next;
  419.     }
  420.     p4_unlock(&(glob->QAVL));
  421.     return(node);
  422. }
  423.  
  424. /*
  425.   this routine frees a queue_node
  426.   */
  427. dealloc_queue_node(node)
  428. struct queue_node *node;
  429. {
  430.     
  431.     p4_lock(&(glob->QAVL));
  432.     node->next = glob->q_avail;
  433.     glob->q_avail = node;
  434.     p4_unlock(&(glob->QAVL));
  435. }
  436.  
  437. /*
  438.   this node adds a tree_node to the pool of work.
  439.   This involves allocating a queue_node and hooking
  440.   it into the pool.  Because the pool is constantly
  441.   being altered by all of the processes, this must
  442.   be a monitor operation.
  443.   */
  444.  
  445. int queue_node(t_node)
  446. struct tree_node *t_node;
  447. {
  448.     struct queue_node *alloc_queue_node();
  449.     struct queue_node *q_node;
  450.     
  451.     q_node = alloc_queue_node();
  452.     q_node->node = t_node;
  453.     q_node->next = glob->pool;
  454.     glob->pool = q_node;
  455.     return(1);            /* new problem */
  456. }
  457.